#ifndef OCTREE_H
#define OCTREE_H

#include <float.h>
#include "BBox.h"
#include <vector>
#include "GeomException.h"

using namespace std;

namespace geom
{
    /** Template class for an Octree mechanism.
     Each Octree object has a list of objects it directly contains, and 
     (maybe) 8 Octree children which can themselves contain objects and other
     octrees.
     \note The code for this class MUST be defined in the .h file because it's
     a template class. For more info see:
     http://www.parashift.com/c++-faq-lite/templates.html#faq-35.13 
     */
    template <typename A> 
        class Octree
        {
            protected:
                /** Axis-aligned bounding box for this octree node*/       
                BBox m_box;
				/** Indicates if this octree has no objects, and neither does any of its descendants*/
				bool empty;				
				/** AABBs for the children nodes */
				BBox m_childrenBoxes[8];

                /** Array of octree children. If an element is set to NULL, 
                  that element does not exist.*/
                Octree** m_children;
                /** Objects this octree node directly contains */
                vector <A> m_objects;

                /** Maximum levels of recursion under this octree node */
                int m_maxChildLevels;

            public:
				/** Gets the Bounding Box for this octree node */
				const BBox & getBBox() const { return m_box;}
                /** Checks if this octree node contains a given object */
                bool contains(const A &object) const
                {
                    return m_box.contains(object);
                }

                /** Adds an object to this node, or possibly to one of its 
                  children */
                void addObject(A object)
                {
                    if(!contains(object))
                        throw GeomException("Tried to add to an octree an object which is bigger or outside said octree");

					empty = false;
					for(int i=0;i<8;++i)
						if(m_children[i]!=NULL && m_childrenBoxes[i].contains(object))
						{
							m_children[i]->addObject(object);
							return;
						}

					m_objects.push_back(object);
                }

                /** Constructs an Octree node 
                  @param box Bounding box for this node
                  @param maxChildLevels Maximum number of levels of recursion
                  under this node */
                Octree(BBox box, int maxChildLevels): m_box(box), m_maxChildLevels(maxChildLevels)
                {
					empty = true;
					float side = m_box.m_side;
					for(int i =-1; i<2; i+=2)
						for(int j =-1;j<2;j+=2)
							for(int k=-1;k<2;k+=2)
							{
								Point3D childBoxCenter(m_box.m_center.x+i*side/4, m_box.m_center.y+j*side/4, m_box.m_center.z+k*side/4);
								m_childrenBoxes[((i+1)/2)*4 + ((j+1)/2)*2 + ((k+1)/2)] = BBox(childBoxCenter,side/2);
							}
                    m_children = new Octree<A>*[8];
                    for(int i=0;i<8;++i)
                        m_children[i] = NULL;
					if(maxChildLevels>0)
						for(int i=0;i<8;++i)
							m_children[i] = new Octree(m_childrenBoxes[i],maxChildLevels-1);
                }

                /** Destructor*/
                ~Octree()
                {
                    for(int i=0; i<8;++i)
                        if(m_children[i]!=NULL)
                            delete m_children[i];

                    delete [] m_children;
                }
				
				/** Finds the intersection between a ray and the octree objects that is nearer to the ray origin */
				bool findNearestIntersection(Ray &r, Point3D *result) const
				{
					if(empty || !m_box.isTraversedBy(r))
						return false;
					
					bool foundAny = false;
					float nearestDistanceFound = FLT_MAX;
					float distance;
					Point3D tempPoint;
					Point3D o = r.origin();
					for(int i=0;i<(int)m_objects.size();++i)
					{
						bool intersects = m_objects[i].getRayIntersectionPoint(r,&tempPoint);
						distance = o.distanceSquared(tempPoint);
						if(intersects && distance < nearestDistanceFound)
						{
							nearestDistanceFound = distance;
							(*result) = tempPoint;
							foundAny=true;
						}
					}
					for(int i=0;i<8;++i)
						if(m_children[i]!=NULL)
						{
							bool pointFound = m_children[i]->findNearestIntersection(r, &tempPoint);
							distance = o.distanceSquared(tempPoint);
							if(pointFound && distance < nearestDistanceFound)
							{	
								nearestDistanceFound = distance;
								(*result) = tempPoint;
								foundAny=true;
							}
						}

					return foundAny;
				}

				/** Checks if there has been any intersection between a ray and this Octree's objects */
				bool findIfIntersection(Ray &r) const
				{
					if(empty || !m_box.isTraversedBy(r))
						return false;
				
					Point3D tempPoint;
					for(int i=0;i<(int)m_objects.size();++i)
					{
						if(m_objects[i].hasPoint(r.origin()))
							continue;

						if( m_objects[i].getRayIntersectionPoint(r,&tempPoint) )
							return true;
					}
					for(int i=0;i<8;++i)
						if(m_children[i]!=NULL)
							if( m_children[i]->findIfIntersection(r) )
								return true;
					return false;
				}
		};
}

#endif
